package 代码随想2._2链表;

/**
 * @author XXX
 * @date 2024-01-14 13:12
 */

import 代码随想录.链表._3设计链表;

/**
 * https://leetcode.cn/problems/design-linked-list/description/
 */
public class _2设计链表 {

}
class ListNode2 {
    int val;
    ListNode2 next;
    ListNode2() {}
    ListNode2(int val) { this.val = val; }
    ListNode2(int val, ListNode2 next) { this.val = val; this.next = next; }
}

class MyLinkedList {

    //size存储链表元素的个数
    int size;
    //虚拟头结点
    ListNode2 head;

    public MyLinkedList() {
        size = 0;
        head = new ListNode2(-1);
    }

    public int get(int index) {
        //如果index非法，返回-1
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode2 currentNode = head;
        //包含一个虚拟头节点，所以查找第 index+1 个节点
        for (int i = 0; i <= index; i++) {
            currentNode = currentNode.next;
        }
        return currentNode.val;
    }

    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        if (index < 0) {
            index = 0;
        }
        size++;
        //找到要插入节点的前驱
        ListNode2 pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        ListNode2 toAdd = new ListNode2(val);
        toAdd.next = pred.next;
        pred.next = toAdd;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        size--;
        if (index == 0) {
            head = head.next;
            return;
        }
        ListNode2 pred = head;
        for (int i = 0; i < index ; i++) {
            pred = pred.next;
        }
        pred.next = pred.next.next;
    }
}